Many complex structures can be represented using graph theory. In graph theory, a graph includes a set of nodes and a set of vertices that connect the nodes to each other. For example, one type of complex structure that can be represented through a graph is an Information Technology (IT) infrastructure. An IT infrastructure includes several physical computing systems and a number of services provided by those systems. When using graphs to topologically represent an IT infrastructure, the nodes are used to represent IT entities within the IT infrastructure and the vertices between the nodes are used to represent the relationships between those entities
When representing a complex structure graphically, it is often useful to perform queries on that structure. One type of query is a topological query. In a topological query, the query input itself is a graph representing a pattern within the full graph structure. The query engine then searches the entire full graph structure to find similar structures. These similar structures found within the full graph structure are then returned to the application that requested the query.
In some cases, it is useful to define what is referred to as a live topological query. Using the IT infrastructure graph as an example, live topological queries involve notifications relating to changes within the IT infrastructure that affect the query result. These notifications are then picked up by listeners that are set to keep a specific query result up-to-date while ongoing changes take place within the IT infrastructure. This is typically done by caching the query result within a cache memory. As changes are made within the IT infrastructure such as the addition and removal of new entities and relationships, these changes are compared with the cached result to determine whether a change is relevant to the live query. If so, then the cache is updated accordingly and the querying application is notified of the change. However, due to the rapidly expanding complexity and size of IT infrastructures, the amount of cache space used to store a full query result can become rather large, consuming large amounts of cache memory.
Throughout the drawings, identical reference numbers designate similar, but not necessarily identical, elements.